package com.samxcode.leetcode;

/**
 * Implement regular expression matching with support for '.' and '*'.
 * 
 * '.' Matches any single character. '*' Matches zero or more of the preceding element.
 * 
 * @author Sam
 *
 */
public class RegularExpressionMatching {

    public static void main(String[] args) {
        System.out.println(isMatch("aab", "c*a*b"));
    }


    public static boolean isMatch(String s, String p) {
        System.out.println(matchDP(s.toCharArray(), p.toCharArray()));
        return matchRecursive(s.toCharArray(), 0, p.toCharArray(), 0);
    }


    private static boolean matchRecursive(char[] s, int si, char[] p, int pi) {
        if (pi == p.length) {
            return s.length == si;
        }
        if (pi < p.length - 1 && p[pi + 1] == '*') {
            if (matchRecursive(s, si, p, pi + 2)) {
                return true;
            }
            while (match(s, si, p, pi)) {
                if (matchRecursive(s, ++si, p, pi + 2)) {
                    return true;
                }
            }
        }
        return match(s, si, p, pi) ? matchRecursive(s, ++si, p, ++pi) : false;
    }


    private static boolean match(char[] s, int si, char[] p, int pi) {
        if (si >= s.length || pi >= p.length) {
            return false;
        }
        if (s[si] == p[pi] || p[pi] == '.') {
            return true;
        }
        return false;
    }


    /**
     * b[i + 1][j + 1]: if s[0..i] matches p[0..j]
     * if p[j] != '*'
     * b[i + 1][j + 1] = b[i][j] && s[i] == p[j]
     * if p[j] == '*', denote p[j - 1] with x,
     * then b[i + 1][j + 1] is true iff any of the following is true
     * 1) "x*" repeats 0 time and matches empty: b[i + 1][j -1]
     * 2) "x*" repeats 1 time and matches x: b[i + 1][j]
     * 3) "x*" repeats >= 2 times and matches "x*x": s[i] == x && b[i][j + 1]
     * '.' matches any single character
     */
    public static boolean matchDP(char[] s, char[] p) {
        boolean[][] b = new boolean[s.length + 1][p.length + 1];
        //base case
        b[0][0] = true;
        for (int i = 1; i < p.length; i += 2) {
            b[0][i + 1] = '*' == p[i] && b[0][i - 1];
        }
        for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < p.length; j++) {
                if (p[j] != '*') {
                    b[i + 1][j + 1] = b[i][j] && (s[i] == p[j] || p[j] == '.');
                } else {
                    if ((j > 0 && b[i + 1][j - 1]) || b[i + 1][j] || (b[i][j + 1]
                            && j > 0 && (s[i] == p[j - 1] || p[j - 1] == '.'))) {
                        b[i + 1][j + 1] = true;
                    }
                }
            }
        }
        return b[s.length][p.length];
    }
}
